<?php
/**
 * User: helloJiu
 * Date: 2021/9/27
 * Time: 10:08
 */

namespace App\Algorithm\DP;


class LengthOfLCS
{
    /**
     * https://leetcode-cn.com/problems/longest-common-subsequence/
     * 使用动态规划求解
     * 输入：text1 = "abcde", text2 = "ace"
     * 输出：3
     * 解释：最长公共子序列是 "ace" ，它的长度为 3 。
     * https://leetcode-cn.com/problems/longest-increasing-subsequence/
     * @param $text1
     * @param $text2
     * @return int
     */
    function longestCommonSubsequence($text1, $text2)
    {
        $dp = [];
        if (empty($text1) || empty($text2)) {
            return 0;
        }
        $len_1 = strlen($text1);
        $len_2 = strlen($text2);
        for ($i = 0; $i <= $len_1; $i++) {
            $dp[$i][0] = 0;
        }

        for ($j = 0; $j <= $len_2; $j++) {
            $dp[0][$j] = 0;
        }

        for ($i = 1; $i <= $len_1; $i++) {
            for ($j = 1; $j <= $len_2; $j++) {
                if ($text1[$i-1] == $text2[$j-1]){
                    $dp[$i][$j] = $dp[$i-1][$j-1] + 1;
                }else{
                    $dp[$i][$j] = max($dp[$i-1][$j], $dp[$i][$j-1]);
                }
            }
        }

        return $dp[$len_1][$len_2];

    }
}